//https://www.bilibili.com/video/BV1d54y1f7B3/?spm_id_from=333.337.search-card.all.click&vd_source=d6fe65f095f01f05591e89d810720ccc
// 2024-10-19

public class P016_排列硬币_二分法 {

    public static void main(String[] args) {
        System.out.println(fun(20));
    }


    // 1-n中间找到个x行，使得前x行求和=n
    private static int fun(int n) {
        int i = 0,j = n;
        while (i <= j) {
            int mid = i + (j-i)/2;
            int cost = (1 + mid)*mid/2;
            if (cost == n) return mid;
            else if (cost > n) j = mid -1;
            else i = mid + 1;
        }
        return j;
    }
}
